package sort;

import java.util.Arrays;

//归并排序
public class MergeSort {
    public static void main(String[] args) {
        int ary[] = {1, 3, 9, 56, 87, 49, 35};
        System.out.println(Arrays.toString(ary));
        System.out.println();

        //调用mergeSort（）方法进行排序
        int[] finalAry = mergeSort(ary, 0 , ary.length - 1);
        System.out.println(Arrays.toString(finalAry));
        System.out.println();
    }

    /**
     * @param ary   原数组
     * @param start 需要被拆分的区间的起始元素下标
     * @param end   需要被拆分的区间的结束元素下标
     * @return 合并后的有序新数组
     */
    public static int[] mergeSort(int[] ary, int start, int end){
        //为防止递归出现‘死循环’，当end与start相同时（发生在尝试对长度为1的
        //数组再拆分），不必再执行
        if (end == start){
            //使用return返回当前片段的新数组
            return new int[]{ary[start]};
        }

        //求数组需要被拆分的区间的中间点
        int mid = start + (end - start) / 2;

        //创建2个新的数组，分别表示拆分之后的左侧区域和右侧区域
        int[] leftAry = mergeSort(ary, start, mid);
        int[] rightAry = mergeSort(ary, mid+1,end);

        //创建新的数组，用于存放合并后的有序结果
        int[] newAry = new int[leftAry.length + rightAry.length];

        //声明变量，l,r,n分别表示leftAry、rightAry、newAry的下标变量
        int l=0, r=0, n=0;

        //当leftAry和rightAry都没有遍历结束之前，一直循环
        while (l < leftAry.length && r < rightAry.length){
            /*//对比2个数组的元素
            if (leftAry[l] <= rightAry[r]){
                newAry[n++] = leftAry[l++];
            }else {
                newAry[n++] = rightAry[r++];
            }*/
            newAry[n++] = leftAry[l] >= rightAry[r] ?
                    leftAry[l++] : rightAry[r++];
        }

        //如果左侧或右侧数组还有剩余，可直接依次全部填充到新数组中
        while (l < leftAry.length){
            newAry[n++] = leftAry[l++];
        }
        while (r < rightAry.length){
            newAry[n++] = rightAry[r++];
        }

        return newAry;
    }
}
